package KS;
//04

public class Floyd_center {



    /**
     * 参数adjMatrix：给定连通图的权重矩阵，
     * 函数功能：返回所有顶点之间的最短距离权重矩阵
     */
    public void getShortestPaths(int[][] adjMatrix) {
        for(int k = 0;k <adjMatrix.length;k++) {
            for(int i = 0;i < adjMatrix.length;i++) {
                for(int j = 0;j < adjMatrix.length;j++) {
                    if(adjMatrix[i][k] != -1 && adjMatrix[k][j] != -1) {
                        int temp = adjMatrix[i][k] + adjMatrix[k][j];  //含有中间节点k的顶点i到顶点j的距离
                        if(adjMatrix[i][j] == -1 || adjMatrix[i][j] > temp)
                            adjMatrix[i][j] = temp;
                    }
                }
            }
        }
    }
    public static void findPlace(String[] data, int[][]  adjMatrix) throws Exception {
        int min = 0;
        int sum = 0;
        int u = 1;
        for(int v = 0; v<adjMatrix.length;v++){

            for(int w =0;w<adjMatrix.length;w++)
                sum += adjMatrix[v][w];
            if(min>=sum){
                min = sum;
                u= v;
            }
        }
        Floyd_center test = new Floyd_center();
        //手动创建图

        test.getShortestPaths(adjMatrix);
        System.out.println("使用Floyd算法得到的所有城市之间的最短距离矩阵为：");
        for(int i = 0;i < adjMatrix.length;i++) {
            for(int j = 0;j < adjMatrix[0].length;j++)
                System.out.print(adjMatrix[i][j]+" ");
            System.out.println();
        }
        System.out.println();
        System.out.println(" 应该选择"+data[u]+"城市为中心,建立通信中心机房" );
        System.out.println("_____________________________");

    }



}








